#include <stdio.h>

void swap(int* e1, int* e2)
{
    int temp = *e1;
    *e1 = *e2;
    *e2 = temp;
}

void AdjustDown(int* arr, int n, int parent)
{
    int child = parent * 2 + 1;
    while(child < n)
    {
        if(child + 1 < n && arr[child + 1] > arr[child])
        child = child + 1;

        if(arr[child] > arr[parent])
        {
            swap(&arr[child], &arr[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        break;
    }
}

void HeapSort(int* a, int n)
{
    for(int i = (n - 2) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }

    for(int end = n - 1; end > 0; end--)
    {
        swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
    }
}

int main()
{
    int arr[] = {9, 10, 54, 74, 65, 13, 95, 46, 25, 30};
    HeapSort(arr, 10);
    for(int i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}